# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/22 22:53
@FileName      : 快速排序.py
@LastEditors   : None
@Editors       : PyCharm
"""
# 不稳定
'''
分治，从最右边选出一个，然后将剩下的数分为大小两组，以此类推
这里要使用两个指针lo,hi
'''


def quick_sort(arr, left, right):
    # 取最后元素作为枢轴值
    pivot = arr[right]
    # 划分子数组
    i = left - 1
    for j in range(left, right + 1):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    # 递归排序子数组
    if left < i - 1:
        quick_sort(arr, left, i - 1)
    if i + 1 < right:
        quick_sort(arr, i + 1, right)

    return arr


# 示例用法
arr = [35, 33, 42, 10, 14, 11, 14, 44, 26, 31]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
